\documentclass[slidestop,compress,serif,trans]{beamer} 
%\usepackage[bars]{beamerthemetree} % Beamer theme v 2.2 
\usetheme{Singapore} % Beamer theme v 3.0 
\usecolortheme{seahorse}
%\usecolortheme{lily}




\usepackage{tikz}
\usetikzlibrary{arrows,backgrounds} 
\usetikzlibrary{automata}
\usetikzlibrary{er}
\usetikzlibrary{trees}
\usetikzlibrary{snakes}
\usetikzlibrary{mindmap}
\usepackage{listings}

\lstset{language=SQL}
\lstset{backgroundcolor=\color[rgb]{0.98,0.98,0.98},columns=fullflexible,frame=single,basicstyle=\small,breaklines=true}


%\beamertemplatetransparentcovereddynamicmedium
\beamertemplateshadingbackground{blue!5}{yellow!10}

\title{Demonstration of CRUD functionality on hierarchical data for PostgreSQL 8.2}
\author{Jonathan Winandy}
\date{\today}

\begin{document}

\frame[plain]{\titlepage}

\section[Outline]{}
\frame{\tableofcontents}

\section{Introduction}
\frame
{
  \frametitle{Introduction}

\begin{block}{}
This demonstration aims to show some exemplary possibilities of hierarchical data processing. 
It tries to generally deal with the ”most extended” hierarchical structure —the direct acyclic graph—, more specifically this presentation deals with PostgreSQL 8.x. However, since this presentation happened to be created in my free time, there is still some leeway for improvements. Hopefully this will be made up soon.
\end{block}

\begin{block}{}
I hope you enjoy this presentation! 
\end{block}


}


\section{Information}
\subsection{Hiearchical data?}
\frame{
\frametitle{Examples of hiearchical data?}


\begin{block}{Filesystem:}
\begin{center}\begin{tikzpicture}[edge from parent fork down] 
\pgftransformxscale{0.7}
\pgftransformyscale{-1} 
\tikzstyle{every node}=[anchor=west] 
\tikzstyle{every edge}=[black,|-,thick,draw] 
  \node (vol) at (0,0) {volume}; 
   \node (var) at (1,0.5) {var} ; 

 \node (www) at (2,1) {www};
 \node (index) at (3,1.5) {index.htm};
 
 \draw[|-,thick] (var.west) -| (vol.south west);
 
 \draw[|-,thick] (www.west) -| (var.south west);
 
 \draw[thick] (index.west) -| (www.south west);
 
 
 \node (etc) at (1,2) {etc} ;
   \draw[|-,thick] (etc.west) -| (vol.south west);
 
 \draw[|-,thick] (var.west) -| (vol.south west);
 
 \draw[|-,thick] (www.west) -| (var.south west);
  \draw[|-,thick] (vol.west) -| +(-1,0);
 
\end{tikzpicture}\end{center}



\end{block}
\begin{block}{Animals:}
\begin{center}\begin{tikzpicture}
\pgftransformxscale{2}
\pgftransformyscale{0.8} 
\tikzstyle{every node}=[fill=black!20,rounded corners] 
\tikzstyle{every edge}=[black,<-,thick,draw] 
  \node (cat) at (0,0) {Cat}; 
  \node (dog) at (1,0) {Dog}; 
  \node (sheep) at (2,0) {Sheep}; 
  \node (cow) at (3,0) {Cow}; 
  \node (pet) at (0.5,1) {Pet} edge (cat) edge (dog) edge (sheep); 
  \node (livestock) at (2.5,1) {Livestock} edge (sheep) edge (cow) edge (dog);
  \node at (1.5,2) {Animals} edge (livestock) edge (pet);
\end{tikzpicture}\end{center}
\end{block}



}



\subsection{What is a DAG?}
\frame
{
  \frametitle{What is a DAG?}

\begin{block}{Wikipedia}
\small In computer science and mathematics, a directed acyclic graph, also called a DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path that starts and ends on v. DAGs appear in models where it doesn't make sense for a vertex to have a path to itself; for example, if an edge u→v indicates that v is a part of u, such a path would indicate that u is a part of itself, which is impossible. Informally speaking, a DAG "flows" in a single direction.
\end{block}

\begin{block}{Our subject of interest?}
DAGs with a root node, that is, DAG which specifically "flows" to only one node.
\begin{center}
\begin{tikzpicture}
 \small
 \tikzstyle{every node}=[fill=black!20,rounded corners] 
\tikzstyle{every edge}=[black,-latex,thick,draw]
\pgftransformxscale{-1}
\pgftransformyscale{0.5}
\node (0) at (0,0) {0} ;
\node (1) at (1,1) {1}  edge (0);
\node (2) at (1,0) {2}  edge (0);
\node (3) at (1,-1) {3}  edge (0);
\node (4) at (2,0.5) {4} edge (1) edge (2) ;
\node (7) at (3,0) {7} edge (4) ;
\node (8) at (3,1) {8} edge (4) ;
\node (9) at (4,0.5) {9} edge (8);
\node (5) at (4,-1) {5} edge (3) edge (7) ;
\node (6) at (5,-1) {6} edge (5) ;
\end{tikzpicture}
\end{center}
\end{block}
}




\subsection{Database structure}
\frame
{
  \frametitle{Database structure}
  \small
  
To store this kind of graphs, we can use this database structure. As an extension, this structure can store as many DAGwRN |DAG with a root node| as we want to. The table optim is here to provide some index functionality base on the nested set model. This table is filled automatically by the database engine via some plPgSQL triggers. 
\begin{center}
\begin{tikzpicture}
{
\pgftransformxshift{0cm}\pgftransformyshift{1cm}
\node[rectangle,anchor=north,draw=black!50,minimum height=2.90cm,minimum width=3cm] (optim) at (0,0) {};
\draw[color=black!50] (-1.1,0) -- (-1.1,-2.90);
\draw[color=black!50] (-1.5,-1.2) -- (1.5,-1.2);

\node[rectangle,anchor=north,draw=black!50,fill=black!20,minimum height=0.6cm,minimum width=3cm] at (0,0) {optim};
\small
\node[anchor=south west] at (-1.1,-1.2) {\textbf{optim\_id}};
\node[anchor=north west] at (-1.1,-1.2) {\begin{minipage}[c]{5cm}
\textbf{edge\_id}\\
optim\_left\\
optim\_right\\
graph\_id
\end{minipage}};
}


{
\pgftransformxshift{-4cm}%\pgftransformyshift{3cm}
\node[rectangle,anchor=north,draw=black!50,minimum height=2.51cm,minimum width=3cm] (edge) at (0,0) {};
\draw[color=black!50] (-1.1,0) -- (-1.1,-2.51);
\draw[color=black!50] (-1.5,-1.2) -- (1.5,-1.2);
\node[rectangle,anchor=north,draw=black!50,fill=black!20,minimum height=0.6cm,minimum width=3cm] at (0,0) {edge};
\small
\node[anchor=south west] at (-1.1,-1.2) {\textbf{edge\_id}};
\node[anchor=north west]  at (-1.1,-1.2) {\begin{minipage}[c]{5cm}
\textbf{node\_id1}\\
\textbf{node\_id2}\\
\textbf{graph\_id}
\end{minipage}  };
}

{\pgftransformxshift{-4cm}\pgftransformyshift{2cm}
\node[rectangle,anchor=north,draw=black!50,minimum height=1.65cm,minimum width=3cm] (graph) at (0,0) {};
\draw[color=black!50] (-1.1,0) -- (-1.1,-1.65);
\draw[color=black!50] (-1.5,-1.2) -- (1.5,-1.2);
\node[rectangle,anchor=north,draw=black!50,fill=black!20,minimum height=0.6cm,minimum width=3cm] at (0,0) {graph};

\small
\node[anchor=south west] at (-1.1,-1.2) {\textbf{graph\_id}};
\node[anchor=north west] at (-1.1,-1.2) {\begin{minipage}[c]{5cm}
\textbf{node\_id}
\end{minipage}  };
}


{
\pgftransformxshift{-8cm}\pgftransformyshift{2cm}
\node[rectangle,anchor=north,draw=black!50,minimum height=1.65cm,minimum width=3cm] (node) at (0,0) {};
\draw[color=black!50] (-1.1,0) -- (-1.1,-1.65);
\draw[color=black!50] (-1.5,-1.2) -- (1.5,-1.2);
\node[rectangle,anchor=north,draw=black!50,fill=black!20,minimum height=0.6cm,minimum width=3cm] at (0,0) {node};
\small
\node[anchor=south west] at (-1.1,-1.2) {\textbf{node\_id}};
\node[anchor=north west] (test1) at (-1.1,-1.2) {\begin{minipage}[c]{5cm}
node\_name
\end{minipage}  };}

\draw[-latex,line width=1pt] (optim) -- (edge);
\draw[-latex,line width=1pt,dashed] (optim) -- (graph);
\draw[-latex,line width=1pt] (edge) -- (graph);
\draw[-latex,line width=1pt] (edge) -- (node);
\draw[-latex,line width=1pt] (edge) -| (node);
\draw[-latex,line width=1pt] (graph) -- (node);

\end{tikzpicture} 
\end{center}

}







\section{CRUD}
\frame
{
  \frametitle{CRUD}
\begin{block}{What is it?}
CRUD represent basic operation we can do on data : 
{\small \begin{tabular}{ll|ll}
\textbf{Operation}  & \textbf{SQL} & \textbf{Operation} & \textbf{SQL} \\ \hline
\textbf{C}reate  &  INSERT & \textbf{U}pdate & UPDATE \\
\textbf{R}ead (\textbf{R}etrieve) & SELECT  &\textbf{D}elete (\textbf{D}estroy) & DELETE
\end{tabular}}

\end{block}  

\begin{block}{What can we test efficiently?}
Not every table get the same interest: \begin{itemize} 
\item The table node is trivial,  then contain 10 nodes from 0 to 9.
\item We will made some try only on 1 graph with 0 as root node.
\item The table optim in automaticly filled.
\end{itemize} Then the table edge will be test.
\end{block}

}



\subsection{Create}
\frame
{
  \frametitle{Create}

\begin{block}{First we can create a graph:}
\begin{center}
\begin{tikzpicture}
 \small
 \tikzstyle{every node}=[fill=black!20,rounded corners] 
\tikzstyle{every edge}=[black,-latex,thick,draw]
\pgftransformxscale{-1}
\pgftransformyscale{0.5}
\node (0) at (0,0) {0} ;
\node (1) at (1,1) {1}  edge (0);
\node (2) at (1,0) {2}  edge (0);
\node (3) at (1,-1) {3}  edge (0);
\node (4) at (2,0.5) {4} edge (1) edge (2) ;
\node (7) at (3,0) {7} edge (4) ;
\node (8) at (3,1) {8} edge (4) ;
\node (9) at (4,0.5) {9} edge (8);
\node (5) at (4,-1) {5} edge (3) edge (7) ;
\node (6) at (5,-1) {6} edge (5) ;
\end{tikzpicture}
\vspace{0.5cm}

\scriptsize
\begin{tabular}{|ll|ll|}
\hline
node\_id1 & node\_id2 & node\_id1 & node\_id2 \\ \hline
1&0&8&4\\
2&0&9&8\\
3&0&5&3\\
4&1&5&7\\
4&2&6&5\\
7&4& &\\ \hline
\end{tabular}
\end{center}

It's important to fill the table edge in the right order, from root to child, recursively.
\end{block}

}

\frame
{
  \frametitle{Create}

\begin{block}{What about cycle ?}
\begin{center}
\begin{tikzpicture}
 \small
 \tikzstyle{every node}=[fill=black!20,rounded corners] 
\tikzstyle{every edge}=[black,-latex,thick,draw]
\pgftransformxscale{-1}
\pgftransformyscale{0.5}
\node (0) at (0,0) {0} ;
\node (1) at (1,1) {1}  edge (0);
\node (2) at (1,0) {2}  edge (0);
\node (3) at (1,-1) {3}  edge (0);
\node (4) at (2,0.5) {4} edge (1) edge (2) ;
\node (7) at (3,0) {7} edge (4) ;
\node (8) at (3,1) {8} edge (4) ;
\node (9) at (4,0.5) {9} edge (8);
\node (5) at (4,-1) {5} edge (3) edge (7) ;
\node (6) at (5,-1) {6} edge (5) ;

\draw[-latex,color=red,thick] (1) .. controls +(1,1) .. (8); 
\end{tikzpicture}
\end{center}
They are basically not accepted by the database which conserve the acyclic property of the graph.
\end{block}
}


\frame
{
  \frametitle{Create}
  \begin{block}{What about unconnected nodes ?}
  \begin{center}
\begin{tikzpicture}
 \small
 \tikzstyle{every node}=[fill=black!20,rounded corners] 
\tikzstyle{every edge}=[black,-latex,thick,draw]
\pgftransformxscale{-1}
\pgftransformyscale{0.5}
\node (0) at (0,0) {0} ;
\node (1) at (1,1) {1}  edge (0);
\node (2) at (1,0) {2}  edge (0);
\node (3) at (1,-1) {3}  edge (0);
\node (4) at (2,0.5) {4} edge (1) edge (2) ;
\node (7) at (3,0) {7} edge (4) ;
\node (8) at (3,1) {8} edge (4) ;
\node (9) at (4,0.5) {9} edge (8);
\node (5) at (4,-1) {5} ;
\tikzstyle{every edge}=[red,-latex,thick,draw]
\node (6) at (5,-1) {6} edge (5) ;

\end{tikzpicture}
\end{center}
Same thing here, they are not accepted by the database because every new node has to get a path to the root. 
  
  \end{block}
  
}






\subsection{Retrieve}

\defverbatim[colored]\testcodea{% 
\begin{lstlisting} 
SELECT node_id1 FROM edge WHERE node_id2 = @1 ;
-- @1 = 4
-- node_id1
-- 8;
-- 7;
\end{lstlisting}}%

\defverbatim[colored]\testcodeb{% 
\begin{lstlisting} 
SELECT node_id2 FROM edge WHERE node_id1 = @1 ;
-- @1 = 4
-- node_id2
-- 1;
-- 2;
\end{lstlisting}}%
\frame
{\frametitle{Retrieve: Basic retrieve (Adjacency list model)}

The following examples use only the table edge, an 'adjacency list model'-like storage.
\begin{block}{Look for direct child of a node:}
\testcodea
\end{block}

\begin{block}{Look for direct parent of a node:}
\testcodeb
\end{block}
}



\defverbatim[colored]\testcodec{% 
\begin{lstlisting} 
SELECT DISTINCT optim2.node_id FROM optim2 JOIN optim2 opt ON optim2.optim_left BETWEEN opt.optim_left+1 AND opt.optim_right WHERE opt.node_id = @1;
-- @1 = 4
-- node_id
-- 5;
-- 6;
-- 7;
-- 8;
-- 9;
\end{lstlisting}}%

\frame
{\frametitle{Retrieve: Advanced retrieve (Nested set model)}

Most of the following examples use the view optim2, which is more or less a join between edge and optim.

\begin{block}{Look for any child of a node:}
\testcodec
\end{block}
}

\defverbatim[colored]\testcoded{% 
\begin{lstlisting} 
SELECT DISTINCT optim2.node_id FROM optim2 WHERE optim_right = optim_left+1;
-- node_id
-- 6;
-- 9;
\end{lstlisting}}%

\frame
{\frametitle{Retrieve: Advanced retrieve (Nested set model)}

\begin{block}{Find all leaf nodes:}
\testcoded
\end{block}
}



\defverbatim[colored]\testcodee{% 
\begin{lstlisting} 
SELECT optim2.optim_id, opt.node_id, opt.optim_left FROM optim2 JOIN optim2 opt ON optim2.optim_left-1 BETWEEN opt.optim_left AND opt.optim_right 
  WHERE optim2.node_id = @1 
ORDER BY optim2.optim_id, opt.optim_left; 
-- @1 = 7
-- optim_id;node_id;optim_left
-- 225;0;1
-- 225;1;22
-- 225;4;23
-- 226;0;1
-- 226;2;8
-- 226;4;9
\end{lstlisting}}%

\frame
{\frametitle{Retrieve: Advanced retrieve (Nested set model)}
\begin{block}{Retrieve path to root:}
\testcodee
\end{block}
}





\defverbatim[colored]\testcodef{% 
\begin{lstlisting}
SELECT DISTINCT optim2.node_id, Count(*)-1 As node_depth FROM optim2 JOIN optim2 opt ON optim2.optim_left BETWEEN opt.optim_left AND opt.optim_right
GROUP BY optim2.node_id, optim2.optim_id; 
-- node_id;node_depth
-- 0;0
-- 1;1
-- ...
-- 4;2
-- 5;2 -- The depth is sometime not unique, normal!
-- 5;4 -- 
-- 6;3
-- 6;5
-- ...
-- 9;4
\end{lstlisting}}%

\frame
{\frametitle{Retrieve: Advanced retrieve (Nested set model)}
\begin{block}{Find depth of nodes:}
\testcodef

\end{block}
}








\defverbatim[colored]\testcodeg{% 
\begin{lstlisting}
SELECT opt.node_id FROM optim2 JOIN optim2 opt ON optim2.optim_left-1 BETWEEN opt.optim_left AND opt.optim_right 
  WHERE optim2.node_id = @1
  GROUP BY opt.node_id
HAVING count(*) = (SELECT count(*) FROM optim2 WHERE node_id = @1) 
ORDER BY min(opt.optim_left);
-- @1 = 9
-- node_id
-- 0
-- 4
-- 8
\end{lstlisting}}%

\frame
{\frametitle{Retrieve: Advanced retrieve (Nested set model)}
\begin{block}{Find complete father's:}
\testcodeg

\end{block}
}



 
 
 


\subsection{Update}
\frame
{
  \frametitle{Update}
  	\begin{block}{Updates are not currently supported!}
  And cause to that, there is a trigger which blocks updates. An update has to be considered as an insertion followed by a deletion (not in every but in most of the cases). There is still some work to do about this, at least a trigger to manage this kind of situation is needed. 
  \end{block}

}

\subsection{Delete}
\frame
{
  \frametitle{Delete}
  
  	\begin{block}{Delete statement is more than enough!}
  		You don’t need to clean the table optim, as after a deletion statement this will be automatically done. Thus, the ”optim index” is updated after the operation. 
  	\end{block}
  
	\begin{block}{Can we delete in cascade?}
	It’s typically forbidden, at the table level. For some reasons, it was mostly relevant to bloc deletion in cascade at table level. Then only leaf node can be deleted at table level. A function should provide optimized cascade deletion, directly in the database. 
		
	
	
	\end{block}
}


\section{Conclusion}
\frame
{
  \frametitle{Conclusion}
    \begin{block}{We reach a good point!}
    	\begin{itemize}
    		\item Basic features already present :
    			\begin{itemize}
    				\item Integrity of DAGwRNs is warranty.
    				\item Index make some queries possible and much faster.
    			\end{itemize}
    		\item This draft is ready for some experimental stuff (beta).	
    	\end{itemize}
    \end{block}
    \begin{block}{But some improvement are needed.}
     	\begin{itemize}
    	\item On edge, delete in cascade, update.
    	\item Improvement on table optim (cache, index, missing values). %, for example cache edge information or include "missing" entries actually available via a view (optim2).
    	\end{itemize}
    \end{block}
  	\begin{block}{And we have to start some tests.}
  	There are still trials to be done with both generated and real data, to check performances of the data structure. 
  	\end{block}

}

\frame[plain]
{

\pgfputat{\pgfxy(5.5,-4.5)}{\pgfbox[center,center]{
\begin{tikzpicture}
\draw[fill=white] (0,0) rectangle +(15,15);


\end{tikzpicture}}}
\pgfputat{\pgfxy(5.5,-4.5)}{\pgfbox[center,center]{\includegraphics[width=14cm]{tag.pdf}}}


}


\end{document}
